//
// Created by yanhai on 2021/1/3.
//

// 直接插入排序

#include <stdio.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

// 直接插入排序的基本操作就是将一个记录插入到已经排好序的有序表中，从而得到一个新的 记录数增1的有序表
// 最好的情况下：本身就是有序的，仅需比较n-1次，移动0次，时间复杂度是O(n)
// 最坏的情况下：本身是逆序的，需要比较 2+3+...+n=(n+2)(n-1)/2次，需要移动3+4+...+n+n+1=(n+4)(n-1)/2
//             时间复杂度为O(n^2)
// 同样为O(n^2)时间复杂度，直接插入排序比冒泡和简单选择排序的性能要好一些。
void insert_sort(int *data, int length)
{
    int i = 0, j = 0;

    for (i = 1; i < length; i++) {
        // 当前的数比前面的有序数列最后一个还小，则要把当前这个数插入到前面的有序数列中
        if (data[i] < data[i - 1]) {
            // 核心代码，将data[i]插入到正确的位置
            int tmp = data[i];
            for (j = i - 1; j >= 0 && data[j] > tmp; j--) {
                data[j + 1] = data[j];    // 向后移动
            }
            // 此时，比tmp大的元素都已经移动到后面去了,j+1的位置就空了出来，来存放tmp
            data[j + 1] = tmp;
        }
    }

}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    insert_sort(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
